#include "tern/Memoizer.h"
#include "../Core/Executor.h"
#include "tern/RaceDetector.h"
#include "klee/Internal/Module/KModule.h"
#include <sys/file.h>

using namespace llvm;
using namespace klee;
using namespace std;

// Defined in TernLandmark.h
extern const char* landmarks[TERN_LANDMARKS_NUM];

Queue::Queue(pthread_cond_t *active, pthread_cond_t *blocking) {
 	inTaskThreadNum = 0;
	outTaskThreadNum = 0;
	activeQueueCondVar = active;
	blockingQueueCondVar = blocking;
	activeThreadQueue.clear();
	blockingThreadQueue.clear();
	deadThreadQueue.clear();
	ids = 0;
}

 void Queue::printDeadQueue() {
	char buf[BASIC_SIZE*1000] = {0};
	int offset = 0;

	offset += sprintf(buf + offset, "\nDead(%d): ", (int)pthread_self());
	for (unsigned i = 0; i < deadThreadQueue.size(); i++) {
		offset += sprintf(buf + offset, "%x, ", deadThreadQueue.at(i));
	}
	offset += sprintf(buf + offset, "\n\n");
	fprintf(stderr, buf);
}

//bool Queue::IsDeadQueueEmpty() {return deadThreadQueue.size() == 0;}

bool Queue::isTidInDeadQueue(int pthreadId) {
	for (unsigned i = 0; i < deadThreadQueue.size(); i++) {
		if (pthreadId == deadThreadQueue.at(i)) {
			return true;
		}
	}

	return false;
}

bool Queue::delPthreadIDFromDead(int pthreadId) {
	assert(isTidInDeadQueue(pthreadId));
	for (unsigned i = 0; i < deadThreadQueue.size(); i++) {
		if (pthreadId == deadThreadQueue.at(i)) {
			deadThreadQueue.erase(deadThreadQueue.begin()+i);
			return true;
		}
	}

	return false;
}

void Queue::addMyselfToDead() {
	printDeadQueue();
	fprintf(stderr, "Queue::addMyselfToDead TID %d MYTID %d SELF %x is added to dead queue with size %u, queue %s\n",
		gettid(), getTidMap(), (int)pthread_self(), (unsigned)deadThreadQueue.size(), PrintTids().c_str());
	fflush(stderr);
	//assert(!isTidInDeadQueue(pthread_self()));
	if (!isTidInDeadQueue(pthread_self()))
		deadThreadQueue.push_back(pthread_self());
}

bool Queue::isTidInActiveQueue(int tid) {
	for (unsigned i = 0; i < activeThreadQueue.size(); i++) {
		if (tid == activeThreadQueue.at(i)) {
			return true;
		}
	}

	return false;
}

bool Queue::isTidInActiveQueue() {
	int tid = tidMap[gettid()];
	for (unsigned i = 0; i < activeThreadQueue.size(); i++) {
		if (tid == activeThreadQueue.at(i)) {
			//fprintf(stderr, "MyTid %d (%d, %d) is in active queue index %u\n", tid, gettid(), tidMap[gettid()], i);
			return true;
		}
	}
	return false;
}

bool Queue::isTidInBlockingQueue() {
	int tid = tidMap[gettid()];
	for (unsigned i = 0; i < blockingThreadQueue.size(); i++) {
		if (tid == blockingThreadQueue.at(i)->getTid()) {
			return true;
		}
	}

	return false;
}

bool Queue::isTidInQueue() {
	return (isTidInActiveQueue() || isTidInBlockingQueue());
}

bool Queue::findPthreadIDInActiveAndUpdate(int tid) {
	for (unsigned i = 0; i < activeThreadQueue.size(); i++) {
		if (tid == activeThreadQueue.at(i)) {
			activeThreadQueue.at(i) = tidMap[gettid()];
			return true;
		}
	}
	return false;
}

// for pthread_join() wake up.
void Queue::insertPthreadIDAfterActiveTail() {
	int tid = pthread_self();
	assert(!isTidInActiveQueue() && "isTidInActiveQueue(tid) == 0");
	activeThreadQueue.push_back(tid);
}

void Queue::insertTidAfterActiveTail(int tid) {
	assert(!isTidInActiveQueue(tid) && "isTidInActiveQueue(tid) == 0");
	activeThreadQueue.push_back(tid);
}

void Queue::insertAfterActiveTail(int tid) {
	assert(!isTidInActiveQueue(tid) && "isTidInActiveQueue(tid) == 0");
	activeThreadQueue.push_back(tid);
}
	
void Queue::insertAfterActiveTail() {
	int tid = tidMap[gettid()];
	assert(!isTidInActiveQueue() && "isTidInActiveQueue(tid) == 0");
	activeThreadQueue.push_back(tid);
}

// for child thread creation, in order to break this order: 
// child is created, and added to active queue tail; parent is at active queue head, but wait for child to creation to be done.
// although this is not so fair to parent, but it is deterministic, and thread creation events are rare, so it is fine.
void Queue::insertBeforeActiveHead() {
	int tid = tidMap[gettid()];
	if (activeThreadQueue.size() > 0)
		assert(activeThreadQueue.at(0) == INVALID_TID_FOR_PTHREAD_CREATE && "This is guaranteed by insertInvalidBeforeActiveHead() called by parent."); 
	assert(!isTidInActiveQueue() && "isTidInActiveQueue(tid) == 0");
	// Handling the start of main process and the start of child thread is different,
	// since the parent process/thread has created an empty position for child thread, 
	// so a child thread only needs to modify the value "at" the 0 th position of the active queue, 
	// while the main process just inserts its own tid into the active queue.
	// Please refer to before_pthread_create().
	if (activeThreadQueue.size() > 0)
		activeThreadQueue.at(0) = tid;
	else
		activeThreadQueue.push_back(tid);
}

void Queue::insertInvalidBeforeActiveHead() {
	activeThreadQueue.insert(activeThreadQueue.begin(), INVALID_TID_FOR_PTHREAD_CREATE);
}

void Queue::insertToActiveHead(int tid) {
	activeThreadQueue.insert(activeThreadQueue.begin(), tid);
}

void Queue::insertAfterBlockingTail(uint64_t syncVarAddr, uint64_t secondSyncVarAddr) {
	int tid = tidMap[gettid()];
	assert(!isTidInBlockingQueue() && "isTidInBlockingQueue(tid) == 0");
	blockingThreadQueue.push_back(new BlockingTidInfo(tid, syncVarAddr, secondSyncVarAddr));
}

int Queue::getActiveHead() {
	if (activeThreadQueue.size() > 0)
		return activeThreadQueue.at(0);
	else
		return -1;
}

std::string Queue::PrintTids() {
	char buf[BASIC_SIZE*5];
	unsigned offset = 0;

	memset(buf, 0, sizeof(buf));
	offset += sprintf(buf+offset, " || ");
	for (unsigned int i = 0; i < activeThreadQueue.size(); i++) {
		offset += sprintf(buf+offset, "%d, ", activeThreadQueue.at(i));
		assert(offset < sizeof(buf));
	}

	offset += sprintf(buf+offset, " | Block: ");
	for (unsigned int i = 0; i < blockingThreadQueue.size(); i++) {
#if __WORDSIZE == 64
		offset += sprintf(buf+offset, "(%d, %llx), ", 
			blockingThreadQueue.at(i)->getTid(), blockingThreadQueue.at(i)->getSyncVarAddr());
#else
		offset += sprintf(buf+offset, "(%d, %llx), ", 
			blockingThreadQueue.at(i)->getTid(), blockingThreadQueue.at(i)->getSyncVarAddr());
#endif
		assert(offset < sizeof(buf));
	}

	assert(offset < sizeof(buf));
	return &(buf[0]);
}

BlockingTidInfo *Queue::getActivatedTidInfo(uint64_t syncVarAddr) {
	BlockingTidInfo *bti;
	unsigned int i = 0;
	
	while (i < blockingThreadQueue.size()) {
		bti = blockingThreadQueue.at(i);
		if (bti->getSyncVarAddr() == syncVarAddr) {	
			return bti;
		}
		i++;
	}

	return NULL;
}

// if activate_num is 0, means move all, 0 is for cond_broadcast
int Queue::activateTids(uint64_t syncVarAddr, int activateNum) {
	BlockingTidInfo *bti;
	unsigned int i = 0;
	int tid;
	int movedNum = 0;
		
	while (i < blockingThreadQueue.size()) {
		bti = blockingThreadQueue.at(i);
		if (bti->getSyncVarAddr() == syncVarAddr) {	
			tid = bti->getTid();
			blockingThreadQueue.erase(blockingThreadQueue.begin()+i);
			delete bti;
			activeThreadQueue.push_back(tid);
			movedNum++;
			if (movedNum == activateNum)
				return tid;
			// do not execute i++ here, because we have removed one.
		} else
			i++;
	}
		
	return -1;
}

bool Queue::isActiveHead() {
	int tid = tidMap[gettid()];
	assert(activeThreadQueue.size() > 0);
	return (tid == activeThreadQueue.at(0));
}

bool Queue::isActiveHeadNoAssert() {
	int tid = tidMap[gettid()];
	if (activeThreadQueue.size() > 0)
		return (tid == activeThreadQueue.at(0));
	else
		return false;
}

bool Queue::isBlockingHead() {
	int tid = tidMap[gettid()];
	assert(blockingThreadQueue.size() > 0);
	return (tid == blockingThreadQueue.at(0)->getTid());
}

bool Queue::isSyncVarInBlockingQueue(uint64_t syncVarAddr) {
	for (unsigned i = 0; i < blockingThreadQueue.size(); i++) {
		if (blockingThreadQueue.at(i)->getSyncVarAddr() == syncVarAddr)
			return true;
	}
	return false;
}

bool Queue::isBlockingHeadWithSyncVar(uint64_t syncVarAddr) {
	int tid = tidMap[gettid()];
	if (blockingThreadQueue.size() == 0)
		return true;			// if no one is blocking, then return true.
		
	unsigned i = 0;
	for (; i < blockingThreadQueue.size(); i++) {
		//fprintf(stderr, "Queue::isBlockingHeadWithSyncVar %u %u %p\n", i, blockingThreadQueue.size(), (void *)blockingThreadQueue.at(i));
		if (blockingThreadQueue.at(i)->getSyncVarAddr() == syncVarAddr)
			break;
	}
	return (tid == blockingThreadQueue.at(i)->getTid());
}

void Queue::delFromActiveHead() {
	assert(isActiveHead());
	activeThreadQueue.erase(activeThreadQueue.begin());
	pthread_cond_broadcast(activeQueueCondVar);
}

void Queue::delFromBlockingQueue(BlockingTidInfo *bti) {
	unsigned i = 0;
	for (; i < blockingThreadQueue.size(); i++) {
		if (blockingThreadQueue.at(i) == bti) {
			blockingThreadQueue.erase(blockingThreadQueue.begin()+i);
			return;
		}
	}
}

void Queue::insertToBlockingHead(BlockingTidInfo *bti) {
	blockingThreadQueue.insert(blockingThreadQueue.begin(), bti);
}

int Queue::delFromBlockingHeadWithSyncVar(uint64_t syncVarAddr) {
	int myTid = -1;		
	unsigned i = 0;
		
	for (; i < blockingThreadQueue.size(); i++) {
		if (blockingThreadQueue.at(i)->getSyncVarAddr() == syncVarAddr)
			break;
	}

	if (blockingThreadQueue.size() > 0 && i < blockingThreadQueue.size()) {
		BlockingTidInfo *bti = blockingThreadQueue.at(i);
		myTid = bti->getTid();
		blockingThreadQueue.erase(blockingThreadQueue.begin()+i);
		delete bti;
	}
	if (myTid >= 0) {
		pthread_cond_broadcast(blockingQueueCondVar);
	}
	return myTid;
}

void Queue::delFromQueue() {
	int tid = tidMap[gettid()];
	for (unsigned i = 0; i < activeThreadQueue.size(); i++) {
		if (tid == activeThreadQueue.at(i)) {
			activeThreadQueue.erase(activeThreadQueue.begin() + i);
			order_print("delFromQueue active Tid %d\n", tid);
			break;
		}
	}
	for (unsigned i = 0; i < blockingThreadQueue.size(); i++) {
		if (tid == blockingThreadQueue.at(i)->getTid()) {
			BlockingTidInfo *bti = blockingThreadQueue.at(i);
			blockingThreadQueue.erase(blockingThreadQueue.begin() + i);
			order_print("delFromQueue blocking Tid %d\n", tid);
			delete bti;
			break;
		}
	}
}

int Queue::getInTaskThreadNum() {
	return inTaskThreadNum;
}

void Queue::setInTaskThreadNum(int newNum) {
	inTaskThreadNum = newNum;
}

int Queue::getOutTaskThreadNum() {
	return outTaskThreadNum;
}

void Queue::setOutTaskThreadNum(int newNum) {
	outTaskThreadNum = newNum;
}

int Queue::getTidMap() {
	assert(tidMap.find(gettid()) != tidMap.end());
	return tidMap[gettid()];
}

int Queue::getTidMap(int tid) {
	assert(tidMap.find(tid) != tidMap.end());
	return tidMap[tid];
}

int Queue::getNextTid() {
    return ids;
}

bool Queue::findTidMap(int tid) {
	if (tidMap.find(tid) != tidMap.end())
		return true;
	return false;
}

void Queue::incTidMap() {
	tidMap[gettid()] = ids++;
}

void Queue::delTidFromMap(int tid) {
	tidMap.erase(tid);
}

void Queue::updateTidMapForFork(int parentTid, int childTid) {
	assert(tidMap.find(parentTid) != tidMap.end());
	tidMap[childTid] = tidMap[parentTid];
	tidMap.erase(parentTid);
}

Memoizer::Memoizer(SchedCache *sc) {
	schedCache = sc;
	condVarForMutex.clear();
	mutexLocked.clear();
	mutexOwner.clear();
	condVarForRWLock.clear();
	rwLocked.clear();
	isInTask.clear();
	windowTidTotalOrder.clear();
	mmzEnterTaskTidOrder.clear();
	memset(&mutex, 0, sizeof(pthread_mutex_t));
	memset(&condVarForActiveTurn, 0, sizeof(pthread_cond_t));
	memset(&condVarForBlockingTurn, 0, sizeof(pthread_cond_t));
	windowConstraintString = "";
	globalWindowSerialNum = 0;

	queue = new Queue(&condVarForActiveTurn, &condVarForBlockingTurn);
	memAccess.loadStoreInstCnt = 0;
	memAccess.addrCnt = 0;
	memAccess.loggingMemAccess = false;

	oBr = NULL;
}

void Memoizer::printMemAccess() {
	if (RECORD_MEM_ACCESS) {
		FILE *f = xfopen(ORDER_LOG, "a");
		long i = 0;
		while (i != memAccess.loadStoreInstCnt) {
			fprintf(f, "%ld	%s\n", i, memAccess.InstToAddrMap[i]);
			i++;
		}

		i = 0;
		while (i < INST_SIZE) {
			memset(memAccess.InstToAddrMap[i], 0, BASIC_SIZE);
			i++;
		}
		memAccess.loadStoreInstCnt = 0;
		fclose(f);
	}
}

void Memoizer::appendTidTotalOrder(const char *funcName, int myTid, int instId, const uint64_t *args, KInstruction *ki, int hookId) {
	// for batch program, we do not need this threadInTask conditional check, because before the main process exits, it is still in task.
#ifdef MEMOIZER_ORDER
	if (IS_BATCH_PROGRAM || threadInTask()) {
#else
	// If we use random schedules, we need to log all the stuff starting from httpd starts,
	// so we do not need to check threadInTask here, since we do not have task for those approaches.
	if (1) {
#endif
		unsigned length = strlen(funcName) + 200 + sizeof(myTid) + sizeof(instId);// + sizeof(args[2]);
		char *s = new char[length];
		assert(s);
		memset(s, 0, length);
		if (args)
			if (ki)
#if __WORDSIZE == 64
				sprintf(s, "%d %d {%s}-%s-%s-hook-%d(%lx)", myTid, instId, funcName, 
					ki->inst->getParent()->getParent()->getNameStr().c_str(),
					ki->inst->getParent()->getNameStr().c_str(), hookId, args[2]);//, queue->PrintTids().c_str());
#else
				sprintf(s, "%d %d {%s}-%s-%s-hook-%d(%llx)", myTid, instId, funcName, 
					ki->inst->getParent()->getParent()->getNameStr().c_str(),
					ki->inst->getParent()->getNameStr().c_str(), hookId, args[2]);//, queue->PrintTids().c_str());
#endif
			else
#if __WORDSIZE == 64
				sprintf(s, "%d %d no-no-hook-%d{%s}(%lx)", myTid, instId, hookId, funcName, args[2]);//, queue->PrintTids().c_str());
#else
				sprintf(s, "%d %d no-no-hook-%d{%s}(%llx)", myTid, instId, hookId, funcName, args[2]);//, queue->PrintTids().c_str());
#endif
		else 
			if (ki)
				sprintf(s, "%d %d {%s}-%s-%s-hook-%d(no)", myTid, instId, funcName,
					ki->inst->getParent()->getParent()->getNameStr().c_str(),
					ki->inst->getParent()->getNameStr().c_str(), hookId);
			else
				sprintf(s, "%d %d no-no-hook-%d{%s}(no)", myTid, instId, hookId, funcName);

#ifdef MEMOIZER_ORDER
		//fprintf(stderr, "s is %s\n", s);
		windowTidTotalOrder.push_back(s);
		schedCache->addTid(s);
#else
		std::ofstream noOrderLog;
		noOrderLog.open(NO_ORDER_LOG, ios_base::app);
		noOrderLog << s << "\n";
		noOrderLog.flush();
		noOrderLog.close();		
#endif
		
	}
}

void Memoizer::appendLandmarkOp(const char *syncEventName, int logType, const uint64_t *args)
{
	FILE *f = NULL;
	char tidFileName[BASIC_SIZE] = {0};
	
	if (logType == 1)
		f = xfopen(SYNC_LOG, "a");
	else if (logType == 0) {
		sprintf(tidFileName, "%s-%d.txt", ORDER_LOG, gettid());
		f = xfopen(tidFileName, "a");
	}else if (logType == 2) {
		sprintf(tidFileName, "%s-window-%d-Tid-%d-%d.txt", ORDER_LOG, 
                        globalWindowSerialNum, gettid(), queue->getTidMap());
		f = xfopen(tidFileName, "a");
	} else
                abort();

	if (logType == 1) {
		for (int i = 0; i < queue->getTidMap(); i++) {
			fprintf(f, "%s", "					");
		}
	}

	// Special processing for cond vars.
	if (logType == 1) {
		fprintf(f, "%d: %s\n", queue->getTidMap(), syncEventName);	
	} else if (logType == 0 || logType == 2)
		fprintf(f, "%s", syncEventName);
	fflush(f);
	fclose(f);
}

void Memoizer::dumpTidsToFile() {
	char totalOrderBuf[RECORD_SIZE] = {0};
	char tidFileName[BASIC_SIZE] = {0};
	char inputItem[BASIC_SIZE] = {0};
	char tmpFile[BASIC_SIZE] = {0};
	int bufOffset = 0;
	sprintf(tmpFile, "%s.tmp", INPUT);
	std::ifstream oldInput(INPUT);
	std::ofstream newInput(tmpFile);

	// append all tids of current window to the window file.
    bufOffset += sprintf(totalOrderBuf, "%u ", (unsigned)windowTidTotalOrder.size());
    for (unsigned i = 0; i < windowTidTotalOrder.size(); i++) {
      bufOffset += sprintf(totalOrderBuf + bufOffset, "%s\n", windowTidTotalOrder.at(i));
      if (bufOffset > 0.8*RECORD_SIZE) {
		 appendLandmarkOp(totalOrderBuf, 2, NULL);
		 memset(totalOrderBuf, 0, RECORD_SIZE);
		 bufOffset = 0;
      }
    }
    appendLandmarkOp(totalOrderBuf, 2, NULL);

	// Append input log for replay.
    sprintf(tidFileName, "%s-window-%d-Tid-%d-%d.txt", 
            ORDER_LOG, globalWindowSerialNum, gettid(), queue->getTidMap());	
	std::string temp =  &(tidFileName[0]);
	windowConstraintString = temp + " " + windowConstraintString;

	// Inc input num.
	int inputNum = 0;
	if (oldInput.is_open()) {
		if (!(oldInput >> inputNum)) {
			fprintf(stderr, "ORDER module failed to read %s\n", INPUT);
			exit(1);
		}
		oldInput.seekg(0);
		oldInput.getline(inputItem, sizeof(inputItem));
	}
	inputNum++;

	newInput << inputNum << " \n";
	newInput << windowConstraintString << "\n";	// Heming: new added schedule will be matched first.
	for (int i = 0; i < inputNum - 1; i++) {
		memset(inputItem, 0, sizeof(inputItem));
		oldInput.getline(inputItem, sizeof(inputItem));
		newInput << inputItem << "\n";
	}	
	fprintf(stderr, "TERN: A new input \"%s\" is added to schedule cache, currently there are %d schedules, please refer to %s\n",
		windowConstraintString.c_str(), inputNum, INPUT);

	oldInput.close();
	newInput.flush();
	newInput.close();
	rename(tmpFile, INPUT);
}

/* The requirements of using setMutexLocked and setMutexUnLocked is:
	setMutexLocked can only be called after mutex is acquired, 
	and setMutexUnLocked can only be called before mutex is released, 
	so that these two function calls do not overlap.
*/
void Memoizer::initCondVarForMutex(uint64_t mutexAddr) {
	if (condVarForMutex.find((long)mutexAddr) == condVarForMutex.end()) {
		condVarForMutex[(long)mutexAddr] = (pthread_cond_t *)malloc(sizeof(pthread_cond_t));
		memset(condVarForMutex[(int)mutexAddr], 0, sizeof(pthread_cond_t));
	}
}

void Memoizer::setMutexLocked(uint64_t mutexAddr) {
	if (mutexLocked.find((long)mutexAddr) != mutexLocked.end())
		assert(mutexLocked[(long)mutexAddr] != 1);
	mutexLocked[(long)mutexAddr] = 1;
	assert(mutexOwner.find((long)mutexAddr) == mutexOwner.end());
	mutexOwner[(long)mutexAddr] = ternMyTid(gettid());
	//fprintf(stderr, "Memoizer::setMutexLocked TID %d set mutex %llx to be locked %d\n", gettid(), mutexAddr, mutexLocked[(long)mutexAddr]);
}

void Memoizer::setMutexUnLocked(uint64_t mutexAddr) {
	//fprintf(stderr, "Memoizer::setMutexLocked TID %d set mutex %llx to be unlocked %d\n", gettid(), mutexAddr, mutexLocked[(long)mutexAddr]);
	//assert(mutexLocked[(long)mutexAddr] == 1);
	mutexLocked[(long)mutexAddr] = 0;
	assert(mutexOwner.find((long)mutexAddr) != mutexOwner.end());
	mutexOwner.erase((long)mutexAddr);
}

bool Memoizer::mutexAvailable(uint64_t mutexAddr) {
	// Heming: because of this think in the beforePthreadCondWait function, I should maintain my own flags to show whether a mutex is available,
	// I should not query the real mutex. The root cause is I can not reach the pthread_cond_wait external call.
	
	// THINK: Heming: there seems to be races here. At this point, threads waiting on the mutex have been waken up,
	// but at this point I have not released the mutex yet since I have not enter the cond_wait external call.

	if (mutexLocked.find((long)mutexAddr) == mutexLocked.end())
		return true;
	else if (mutexLocked[(long)mutexAddr] == 0)
		return true;
	else if (mutexLocked[(long)mutexAddr] == 1)
		return false;
	else
		assert(false);

	return false;
	
/*	if (pthread_mutex_trylock((pthread_mutex_t *)mutexAddr) != 0) {
		return false;
	}
	else {
		pthread_mutex_unlock((pthread_mutex_t *)mutexAddr);
		return true;
	}*/	
}

void Memoizer::initCondVarForRWLock(uint64_t rwLockAddr) {
	if (condVarForRWLock.find((long)rwLockAddr) == condVarForRWLock.end()) {
		condVarForRWLock[(long)rwLockAddr] = (pthread_cond_t *)malloc(sizeof(pthread_cond_t));
		memset(condVarForRWLock[(int)rwLockAddr], 0, sizeof(pthread_cond_t));
	}
}

// Set rwLocked > 0 means read locked, WRITE_LOCKED means write locked.
void Memoizer::setReadLocked(uint64_t rwLockAddr) {
	if (rwLocked.find((long)rwLockAddr) != rwLocked.end())
		assert(rwLocked[(long)rwLockAddr] != WRITE_LOCKED);
	rwLocked[(long)rwLockAddr]++;
	//fprintf(stderr, "Memoizer::seReadLocked MYTID %d TID %d set readlock %llx to be locked %d\n", ternMyTid(gettid()), gettid(), rwLockAddr, rwLocked[(long)rwLockAddr]);
}

void Memoizer::setWriteLocked(uint64_t rwLockAddr) {
	if (rwLocked.find((long)rwLockAddr) != rwLocked.end())
		assert(rwLocked[(long)rwLockAddr] == 0);
	rwLocked[(long)rwLockAddr] = WRITE_LOCKED;
	//fprintf(stderr, "Memoizer::setWriteLocked MYTID %d TID %d set writelock %llx to be locked %d\n", ternMyTid(gettid()), gettid(), rwLockAddr, rwLocked[(long)rwLockAddr]);
}

void Memoizer::setRWUnLocked(uint64_t rwLockAddr) {
	assert(rwLocked[(long)rwLockAddr] > 0);
	if (rwLocked[(long)rwLockAddr] == WRITE_LOCKED)
		rwLocked[(long)rwLockAddr] = 0;
	else
		rwLocked[(long)rwLockAddr]--;
}

bool Memoizer::isReadLocked(uint64_t rwLockAddr) {
	if (rwLocked.find((long)rwLockAddr) == rwLocked.end())
		return false;
	else if (rwLocked[(long)rwLockAddr] > 0 && rwLocked[(long)rwLockAddr] != WRITE_LOCKED)
		return true;
	else
		return false;
}

bool Memoizer::isWriteLocked(uint64_t rwLockAddr) {
	if (rwLocked.find((long)rwLockAddr) == rwLocked.end())
		return false;
	else if (rwLocked[(long)rwLockAddr] == WRITE_LOCKED)
		return true;
	else
		return false;
}

bool Memoizer::isRWUnLocked(uint64_t rwLockAddr) {
	if (!isReadLocked(rwLockAddr) && !isWriteLocked(rwLockAddr))
		return true;
	else
		return false;
}

int Memoizer::waitForBlockingTurn(uint64_t syncVarAddr)
{
	struct timespec ts;

	int i = 0;
	while (!queue->isBlockingHeadWithSyncVar(syncVarAddr)) {
		i++;
		if (i%1000 == 0) {
			order_print("waitForBlockingTurn %d %s.\n", queue->getTidMap(), queue->PrintTids().c_str());
		}
		clock_gettime(CLOCK_REALTIME, &ts);
		ts.tv_sec += 1;
		pthread_cond_timedwait(&condVarForBlockingTurn, &mutex, &ts);
	}
	order_print("got blocking turn %d %s\n", queue->getTidMap(), queue->PrintTids().c_str());
	return 0;
}

// Return the tid maintained by myself. The input tid is the system tid.
int Memoizer::ternMyTid(int tid) {
	int myTid;

	if(!queue->findTidMap(tid))
		return -1;
	myTid = queue->getTidMap(tid);
	assert(myTid >= 0);
	return myTid;
}

void Memoizer::appendWindowString(std::string str) {
	windowConstraintString += str + " ";
}

int Memoizer::beforePthreadMutexLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d enters before_pthread_mutex_lock for mutex %llx, queue %s\n", 
		//queue->getTidMap(), args[2], queue->PrintTids().c_str());

	struct timespec ts;
	int result = -1;

	initCondVarForMutex(args[2]);

	/* TODO: Heming, we can do some optimization for performance here,
		if the mutex is available, we do not need to release the lock, just skip the llvm instruction. */
	do {
		waitForTurn(funcName, 0);
		if (!mutexAvailable(args[2])) {
			queue->delFromActiveHead();
			queue->insertAfterBlockingTail(args[2]);
			clock_gettime(CLOCK_REALTIME, &ts);
			ts.tv_sec += 1;
			order_print("MyTid %d blocks on cond var for mutex %llu\n", queue->getTidMap(), args[2]);
			// Heming 2010-8-12: change from timedwait to cond wait, since if this thread is not signaled to wake up, then the lock is still unavailable.
			//result = pthread_cond_timedwait(condVarForMutex[(int)args[2]], &mutex, &ts);
			result = pthread_cond_wait(condVarForMutex[(int)args[2]], &mutex);
			order_print("MyTid %d wakes up on cond var for mutex %llu\n", queue->getTidMap(), args[2]);
		} else {
			//fprintf(stderr, "MyTid %d, Tid %d BREAK for mutex %llx, result %d, queue %s\n", 
				//queue->getTidMap(), gettid(), args[2], result, queue->PrintTids().c_str());
			break;
		}
		//fprintf(stderr, "MyTid %d, Tid %d while loop for mutex %llx, result %d, queue %s\n", 
			//queue->getTidMap(), gettid(), args[2], result, queue->PrintTids().c_str());
	} while (true);
	return 0;
}

int Memoizer::beforePthreadMutexUnLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d TID %d enter before_pthread_mutex_unlock %llx, %llx, hookId %d\n", queue->getTidMap(), gettid(), args[0], args[2], hookId);fflush(stderr);
	waitForTurn(funcName, 0);
	setMutexUnLocked(args[2]);
	giveUpTurn(funcName, 0);
	appendLandmarkOp(funcName, 1, args);
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	//order_print("Tid %d MyTid %d leaves before_pthread_mutex_unlock(%llx)\n", gettid(), queue->getTidMap(), args[2]);

	return 0;
}

int Memoizer::beforePthreadRWLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, bool isWriteLock, int hookId) {
	uint64_t rwLockAddr = args[2];

	/*fprintf(stderr, "MyTid %d enters beforePthreadRWLock(%d, %d) for mutex %llx, queue %s\n", 
		queue->getTidMap(), isWriteLock, isRWUnLocked(rwLockAddr), rwLockAddr, queue->PrintTids().c_str());*/
	initCondVarForRWLock(rwLockAddr);
	do {
		waitForTurn(funcName, 0);
		if ((isWriteLock && !isRWUnLocked(rwLockAddr)) || (!isWriteLock && isWriteLocked(rwLockAddr))) {
			queue->delFromActiveHead();
			queue->insertAfterBlockingTail(rwLockAddr);
			pthread_cond_wait(condVarForRWLock[(long)rwLockAddr], &mutex);
		} else {
			break;
		}
	} while (true);

	/*fprintf(stderr, "MyTid %d enters beforePthreadRWLock RETURN for mutex %llx, queue %s\n", 
		queue->getTidMap(), rwLockAddr, queue->PrintTids().c_str());*/
	return 0;
}

int Memoizer::beforePthreadRWUnLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d TID %d enter before_pthread_mutex_unlock %llx, %llx, hookId %d\n", queue->getTidMap(), gettid(), args[0], args[2], hookId);fflush(stderr);
	waitForTurn(funcName, 0);
	setRWUnLocked(args[2]);
	giveUpTurn(funcName, 0);
	appendLandmarkOp(funcName, 1, args);
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	return 0;
}

int Memoizer::beforePthreadCreate(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	waitForTurn(funcName, 0);
	appendLandmarkOp(funcName, 1, args);
	giveUpTurn(funcName, 0);
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);

	// A trick: in order to let my child thread to get the next turn.
	// This is also guaranteed by the thread creation is strictly sequential (guarantee by the semaphore in thread creation).
	queue->insertInvalidBeforeActiveHead();		

        if(get_option(tern, detect_race))
            theRaceDetector->onCreateThread(queue->getTidMap(),
                                            queue->getNextTid());
	return 0;
}

int Memoizer::beforeAcceptSocket(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	waitForTurn(funcName, 0);
	appendLandmarkOp(funcName, 1, args);
	queue->delFromActiveHead();
	queue->insertAfterBlockingTail(SOCKET_SYNC_VAR_BASE + queue->getTidMap());		// For pthread_join, use the child pthread id as blocking var.
	// Heming: it may be a big problem to assign an order to accept().
	//appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	//fprintf(stderr, "Memoizer::beforeAcceptSocket MyTid %d: %s() starts to leave\n", queue->getTidMap(), funcName);
	return 0;
}

int Memoizer::beforeSleep(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
#ifdef HANDLE_SLEEP
	beforeAcceptSocket(funcName, args, ki, instId, hookId);
	order_print("Tid %d MyTid %d enters before_sleep\n", gettid(), queue->getTidMap());	
#endif
	return 0;
}

int Memoizer::beforeSignalWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	beforeAcceptSocket(funcName, args, ki, instId, hookId);
	return 0;
}

int Memoizer::beforePthreadJoin(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d: before_pthread_join(%llx) starts to work\n", queue->getTidMap(), args[2]);fflush(stderr);
	waitForTurn(funcName, 0);
	appendLandmarkOp(funcName, 1, args);

	if (!queue->isTidInDeadQueue(args[2])) {
		queue->delFromActiveHead();
		queue->insertAfterBlockingTail(args[2]);		// For pthread_join, use the child pthread id as blocking var.
		//fprintf(stderr, "MyTid %d: before_pthread_join(%llx) blocks on queue\n", queue->getTidMap(), args[2]);fflush(stderr);

	} else {
		//order_print("MyTid %d: before_pthread_join(%llx) thread is in dead queue %s\n", queue->getTidMap(), args[2], queue->PrintTids().c_str());
	}

	//order_print("MyTid %d: before_pthread_join(%llx) finish to work %s\n", queue->getTidMap(), args[2], queue->PrintTids().c_str());
	return 0;
}

int Memoizer::beforePthreadCondSignal(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	waitForTurn(funcName, 0);
	// NOTE: take care, if the place I put the thread into the active queue is between the mutex lock and unlock of one thread,
	// and this mutex is the mutex for the cond var, then there is deadlock: the activated thread is waiting for mutex, and got the turn;
	// and the thread is going to unlock got the mutex, and waiting for the turn.
	uint64_t condVarAddr = args[2];
	//queue->activateTids(args[2], 1);
	BlockingTidInfo *bti = queue->getActivatedTidInfo(condVarAddr);
	if (bti) {
		uint64_t mutexAddr = bti->getSecondSyncVarAddr();
		if (mutexAvailable(mutexAddr)) {
			int tid = bti->getTid();
			queue->delFromBlockingQueue(bti);
			// Insert o active head, to avoid the tid before me to lock the mutex, and then I meet the same case: I am between others' lock and unlock.
			queue->insertToActiveHead(tid);
			delete bti;
		} else {
			bti->setSyncVarAddr(mutexAddr, 0);
			queue->delFromBlockingQueue(bti);
			// Insert o blocking head, since I am a hidden locker when I wake up, this is also to avoid circle.
			queue->insertToBlockingHead(bti);
		}
	}
	appendLandmarkOp(funcName, 1, args);

// Heming: the same as Lamport.cpp, do not move the tid to tail, since it is going to release the lock.
//giveUpTurn(funcName, 0);

	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	fprintf(stderr, "Tid %d leaves before_pthread_cond_signal\n", queue->getTidMap());

	return 0;
}

int Memoizer::beforePthreadCondBroadcast(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	waitForTurn(funcName, 0);
	// TODO: the same thing as cond signal in activating tids.
	queue->activateTids(args[2], 0);
	appendLandmarkOp(funcName, 1, args);

	// Heming: the same as Lamport.cpp, do not move the tid to tail, since it is going to release the lock.
	//giveUpTurn(funcName, 0);

	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);

	return 0;
}

int Memoizer::beforePthreadCondWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	/*fprintf(stderr, "before_pthread_cond_wait START! MYTID %d TID %d, mutex %llx, queue %s\n", queue->getTidMap(), gettid(), args[3], queue->PrintTids().c_str());
	fflush(stderr);*/

	waitForTurn(funcName, 0);

	/*fprintf(stderr, "before_pthread_cond_wait GOT TURN! MYTID %d TID %d, mutex %llx, queue %s\n", queue->getTidMap(), gettid(), args[3], queue->PrintTids().c_str());
	fflush(stderr);*/
	
	appendLandmarkOp("before_pthread_cond_wait", 1, args);
	queue->delFromActiveHead();
	queue->insertAfterBlockingTail(args[2], args[3]);
	if (strcmp(funcName, "pthread_cond_wait") == 0)			// pthread_cond_timedwait also uses this function, but we do not record its order.
		appendTidTotalOrder(TERN_CONDWAIT_BEFORE, queue->getTidMap(), instId, args, ki, hookId);
	else if (strcmp(funcName, "pthread_cond_timedwait") == 0)
		appendTidTotalOrder(TERN_TIMEDWAIT_BEFORE, queue->getTidMap(), instId, args, ki, hookId);

	// Here we must broadcast all blocking threads on the mutex, since cond wait will unlock the mutex.
	//fprintf(stderr, "MyTid %d broadcast on cond var for mutex %llu\n", queue->getTidMap(), args[3]);
	// Heming: do we need to activate tids from blocking queue here? Yes!
	queue->activateTids(args[3], 0);
	setMutexUnLocked(args[3]);
	//fprintf(stderr, "MyTid %d after broadcast on cond var for mutex %llu, queue %s\n", queue->getTidMap(), args[3], queue->PrintTids().c_str());
	pthread_cond_broadcast(condVarForMutex[(int)args[3]]);

	// THINK: Heming: there seems to be races here. At this point, threads waiting on the mutex have been waken up,
	// but at this point I have not released the mutex yet since I have not enter the cond_wait external call.
	// I have solved this problem by using setMutexUnLocked() above.

	/*fprintf(stderr, "before_pthread_cond_wait RETURN! MYTID %d TID %d SELF %x, mutex %llx, queue %s\n", 
		queue->getTidMap(), gettid(), (int)pthread_self(),  args[3], queue->PrintTids().c_str());
	fflush(stderr);*/
	
	return 0;
}

int Memoizer::beforePthreadCondTimedWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	beforePthreadCondWait(funcName, args, ki, instId, hookId);
	order_print("Tid %d MyTid %d enters before_pthread_cond_timedwait\n", gettid(), queue->getTidMap());

	// Heming: increase the timeout value for pthread_cond_timedwait, and it does not affect the sematics of applications.
	// Otherwise, the pbzip2 will have same-cst-diff-sched problem, since timedwait is pretty random.
	struct timespec *ts = (struct timespec *)args[4];
	//struct timeval tnow;
	//gettimeofday(&tnow, NULL);
	ts->tv_sec = ts->tv_sec + 60;	// timeout is 60 seconds.
	//ts->tv_nsec = tnow.tv_usec*1000;

	return 0;
}

int Memoizer::beforePthreadBarrierWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	waitForTurn(funcName, 0);
	appendLandmarkOp("before_pthread_barrier_wait", 1, args);
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	queue->delFromActiveHead();
	queue->insertAfterBlockingTail(args[2]);

        // YJF: need this because this code doesn't call giveUpTurn()
        if(get_option(tern, detect_race))
            theRaceDetector->onReleaseTurn(ternMyTid(gettid()));

	return 0;
}

int Memoizer::afterPthreadMutexLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d TID %d enter after_pthread_mutex_lock %llx, %llx\n", queue->getTidMap(), gettid(), args[0], args[2]);
	setMutexLocked(args[2]);
	giveUpTurn(funcName, 0);
	appendLandmarkOp("lock", 1, args);
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	return 0;
}

int Memoizer::afterPthreadMutexUnLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d enter after_pthread_mutex_unlock %llx, %llx\n", queue->getTidMap(), args[0], args[2]);fflush(stderr);
	queue->activateTids(args[2], 0);
	pthread_cond_broadcast(condVarForMutex[(int)args[2]]);
	return 0;
}

int Memoizer::afterPthreadRWLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, bool isWriteLock, int hookId) {
	//fprintf(stderr, "MyTid %d TID %d enter afterPthreadRWLock(%d) %llx, %llx\n", queue->getTidMap(), gettid(), isWriteLock, args[0], args[2]);
	uint64_t rwLockAddr = args[2];

	if (isWriteLock)
		setWriteLocked(rwLockAddr);
	else
		setReadLocked(rwLockAddr);
	giveUpTurn(funcName, 0);
	appendLandmarkOp(funcName, 1, args);
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	return 0;
}

int Memoizer::afterPthreadRWUnLock(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d enter afterPthreadRWUnLock %llx, %llx\n", queue->getTidMap(), args[0], args[2]);fflush(stderr);
	uint64_t rwLockAddr = args[2];

	if (isRWUnLocked(rwLockAddr)) {
		queue->activateTids(rwLockAddr, 0);
		pthread_cond_broadcast(condVarForRWLock[(long)rwLockAddr]);
	}
	return 0;
}

int Memoizer::afterPthreadCreate(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	// NOP. Not a blocking function.

	return 0;
}

int Memoizer::afterAcceptSocket(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	/*fprintf(stderr, "Memoizer::afterAcceptSocket TID %d MyTid %d: %s() starts to work, queue %s\n", 
		gettid(), queue->getTidMap(), funcName, queue->PrintTids().c_str());*/
	waitForBlockingTurn(SOCKET_SYNC_VAR_BASE + queue->getTidMap());
	queue->delFromBlockingHeadWithSyncVar(SOCKET_SYNC_VAR_BASE + queue->getTidMap());
	queue->insertAfterActiveTail();

	/*fprintf(stderr, "Memoizer::afterAcceptSocket 2 TID %d MyTid %d: %s() starts to work, queue %s\n", 
		gettid(), queue->getTidMap(), funcName, queue->PrintTids().c_str());*/

	waitForTurn(funcName, 0);

	/*fprintf(stderr, "Memoizer::afterAcceptSocket 3 TID %d MyTid %d: %s() starts to work, queue %s\n", 
		gettid(), queue->getTidMap(), funcName, queue->PrintTids().c_str());*/

	giveUpTurn(funcName, 0);

	appendLandmarkOp(funcName, 1, args);
	//fprintf(stderr, "Memoizer::afterAcceptSocket RETURN MyTid %d: %s() starts to work, queue %s\n", queue->getTidMap(), funcName, queue->PrintTids().c_str());
	return 0;
}

int Memoizer::afterSleep(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
#ifdef HANDLE_SLEEP
	order_print("Tid %d MyTid %d enters after_sleep\n", gettid(), queue->getTidMap());	
	afterAcceptSocket(funcName, args, ki, instId, hookId);
#endif
	return 0;
}

int Memoizer::afterSignalWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	afterAcceptSocket(funcName, args, ki, instId, hookId);
	return 0;
}

int Memoizer::afterPthreadJoin(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	//fprintf(stderr, "MyTid %d: after_pthread_join(%llx) starts to work\n", queue->getTidMap(), args[2]);fflush(stderr);

	//order_print("MyTid %d: after_pthread_join(%llx) starts to work\n", queue->getTidMap(), args[2]);
	if (!queue->isTidInActiveQueue()) {
		waitForBlockingTurn(args[2]);
		queue->delFromBlockingHeadWithSyncVar(args[2]);
		if (!queue->findPthreadIDInActiveAndUpdate(args[2]))
			assert(false && "after_pthread_join");
	} else {
		// If current thread is in active head, then the waited thread has already been dead,
		// and in this case, current thread is not put into blocking queue, so we do not restore it from blocking queue.
		// EMPTY
	}

	// Do not forget this!
	waitForTurn(funcName, 0);
	giveUpTurn(funcName, 0);
	appendLandmarkOp("after_pthread_join", 1, args);

	// Heming: need to log the tid total order here, since the before_pthread_join does not log this.
	appendTidTotalOrder(funcName, queue->getTidMap(), instId, args, ki, hookId);
	assert(queue->delPthreadIDFromDead(args[2]));		// this is to avoid pthread id repeating problem.
	return 0;
}

int Memoizer::afterPthreadCondSignal(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	// NOP. Not a blocking function.
	//order_print("Tid %d leaves after_pthread_cond_signal(%llx, %llx)\n", queue->getTidMap(), args[2], args[3]);

	return 0;
}

int Memoizer::afterPthreadCondBroadcast(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	// NOP. Not a blocking function.

	return 0;
}

int Memoizer::afterPthreadCondWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	int trylockOK = 0;
	int i = 0;
	
	fprintf(stderr, "after_pthread_cond_wait start! MYTID %d TID %d self %x, mutex %llx, queue %s\n", 
		queue->getTidMap(), gettid(), (int)pthread_self(), args[3], queue->PrintTids().c_str());
	fflush(stderr);
	// Heming: must not use wait_for_active_turn() here.
	while (!queue->isActiveHeadNoAssert() || trylockOK != 0) {
		if (queue->isActiveHeadNoAssert() && trylockOK != 0) {
			order_print("Tid %d MyTid %d after_pthread_cond_wait got turn, but does not get mutex, release turn\n", gettid(), queue->getTidMap());
			giveUpTurn(funcName, 0);
		}

		unLock();
		if (trylockOK == 0) {
			// Heming: do we need to activate tids from blocking queue here? Yes!
			pthread_mutex_unlock((pthread_mutex_t *)args[3]);
		}
		i++;
		if (i%10 == 0) {
			fprintf(stderr, "after_pthread_cond_wait sleep! %d %s\n", queue->getTidMap(), queue->PrintTids().c_str());
		}
		usleep(SLEEP_TIME);
		trylockOK = pthread_mutex_trylock((pthread_mutex_t *)args[3]);
		lock();
	}

	setMutexLocked(args[3]);

	// OK, I got the turn and I am the guy which should be waken up.
	appendLandmarkOp("after_pthread_cond_wait", 1, args);
	if (strcmp(funcName, "pthread_cond_timedwait") == 0)
		appendTidTotalOrder(TERN_TIMEDWAIT_AFTER, queue->getTidMap(), instId, args, ki, hookId);
	else if (strcmp(funcName, "pthread_cond_wait") == 0)
		appendTidTotalOrder(TERN_CONDWAIT_AFTER, queue->getTidMap(), instId, args, ki, hookId);

	// Heming: do not give up turn, and go on to do the next operation, in order to avoid the deadlock  below:
	/* I wake up from cond_wait, and I am going to call unlock for the mutex as the next step, but other threads
		are on the active queue (then they are ahead of me in the queue since I am moved to the tail), 
		and they are waiting for me to release the mutex. 
	*/
	//giveUpTurn(funcName, 0);

	fprintf(stderr, "after_pthread_cond_wait RETURN! MYTID %d TID %d self %x, mutex %llx, queue %s\n", 
		queue->getTidMap(), gettid(), (int)pthread_self(), args[3], queue->PrintTids().c_str());
	fflush(stderr);
	
	return 0;
}

int Memoizer::afterPthreadCondTimedWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	int trylockOK = 0;

	/*fprintf(stderr, "Tid %d MyTid %d self %x enters after_pthread_cond_timedwait, args 0 %lld, queue %s\n", 
		gettid(), queue->getTidMap(), (int)pthread_self(), args[0], queue->PrintTids().c_str());*/
	
	// Heming: do not trust the return value of pthread_cond_timedwait, trust my own queue structure.
	if (queue->isTidInActiveQueue()) {
		afterPthreadCondWait(funcName, args, ki, instId, hookId);
		//assert(false);
	} else {
			assert(queue->isTidInBlockingQueue());
			
			//waitForBlockingTurn();
			// Heming: must not use waitForBlockingTurn() here. Deadlock, since the thread is holding the app level mutex. 
			// do not need to check the trylockOK flag here, since even we leave this loop, there is another loop later 
			// to guarantee we have grabbed the lock before we leave this timedwait function.
			int i = 0;
			while (!queue->isBlockingHeadWithSyncVar(args[2])) {	// check blocking head.
				unLock();
				if (trylockOK == 0) {
					pthread_mutex_unlock((pthread_mutex_t *)args[3]);
				}
				usleep(SLEEP_TIME);
				trylockOK = pthread_mutex_trylock((pthread_mutex_t *)args[3]);
				lock();
			}
			
			queue->delFromBlockingHeadWithSyncVar(args[2]);
			queue->insertAfterActiveTail();

		// Heming: must not use wait_for_active_turn() here. Deadlock, since the thread is holding the app level mutex.
		i = 0;
		while (!queue->isActiveHeadNoAssert() || trylockOK != 0) {		// check active head.
			if (queue->isActiveHeadNoAssert() && trylockOK != 0) {
				order_print("Tid %d MyTid %d after_pthread_cond_timedwait got turn, but does not get mutex, release turn\n", gettid(), queue->getTidMap());
				giveUpTurn(funcName, 0);
			}

			unLock();
			if (trylockOK == 0) {
				pthread_mutex_unlock((pthread_mutex_t *)args[3]);
			}
			i++;
			if (i%1000 == 0) {
				//fprintf(stderr, "after_pthread_cond_timedwait sleep active! %x %d %s\n", (int)pthread_self(), queue->getTidMap(), NULL);
			}
			usleep(SLEEP_TIME);
			trylockOK = pthread_mutex_trylock((pthread_mutex_t *)args[3]);
			lock();
		}

		setMutexLocked(args[3]);

		// OK, got the turn, do the logging.
		appendLandmarkOp("after_pthread_cond_timedwait", 1, args);
		appendTidTotalOrder(TERN_TIMEDWAIT_AFTER, queue->getTidMap(), instId, args, ki, hookId);

		// Heming: do not give up turn, and go on to do the next operation, in order to avoid the deadlock  below:
		/* I wake up from cond_wait, and I am going to call unlock for the mutex as the next step, but other threads
			are on the active queue (then they are ahead of me in the queue since I am moved to the tail), 
			and they are waiting for me to release the mutex.
		*/
		//giveUpTurn(funcName, 0);
	}	

	order_print("leave after_pthread_cond_timedwait %d %d %s\n", gettid(), queue->getTidMap(), queue->PrintTids().c_str());
	return 0;
}

int Memoizer::afterPthreadBarrierWait(const char *funcName, const uint64_t *args, KInstruction *ki, int instId, int hookId) {
	order_print("MyTid %d: after_pthread_barrier_wait() starts to work\n", queue->getTidMap());
	//waitForBlockingTurn(args[2]);
	int tid = -1;

	// wake up all threads blocking on this barrier.
	while ((tid = queue->delFromBlockingHeadWithSyncVar(args[2])) != -1) {
		queue->insertAfterActiveTail(tid);
	}

	waitForTurn(funcName, 0);
	giveUpTurn(funcName, 0);

	appendLandmarkOp("after_pthread_barrier_wait", 1, args);
	return 0;
	
}

// Make this to be in deterministic order control. 
// But this does not affect x86 program, so we do not log its total tid order.

// Do the wait-for-turn at before hook.
void Memoizer::ternBeforeMakeSymbolic(const char *cacheName, KInstruction *ki, int instId, int hookId) {
#ifdef MEMOIZER_ORDER
	// Wait for turn here, and release the turn at afterMakeSymbolic to avoid race.
	//fprintf(stderr, "Memoizer::ternBeforeMakeSymbolic queue %s\n", queue->PrintTids().c_str());
	waitForTurn(__FUNCTION__, 0);
	char buf[BASIC_SIZE] = {0};
	sprintf(buf, "%s-%s", TERN_SYMBOLIC_LANDMARK, cacheName);
	fprintf(stderr, "Memoizer::ternBeforeMakeSymbolic %s\n", buf);
	appendTidTotalOrder(buf, queue->getTidMap(), instId, NULL, ki, hookId);
#endif
}

// Do the update-queue at after hook.
void Memoizer::ternAfterMakeSymbolic() {
#ifdef MEMOIZER_ORDER
	giveUpTurn(__FUNCTION__, 0);
#endif
}

void Memoizer::appStart() {
	if (IS_BATCH_PROGRAM)
		assert(TASK_WINDOW_SIZE == 1);
	schedCache->loadCache();
	if (RECORD_MEM_ACCESS) {
		for (int i = 0; i < INST_SIZE; i++) {
			memAccess.InstToAddrMap[i] = new char[BASIC_SIZE];
			if (memAccess.InstToAddrMap[i] == NULL)
				exit(1);
			memset(memAccess.InstToAddrMap[i], 0, BASIC_SIZE);
		}
		//srand(time(NULL));
	}
	threadCreateEnd(0, 0);	// (view main process starts as a thread create).
}

void Memoizer::appEnd(int *info) {
	threadExit(info, 0);
}

void Memoizer::taskStart(int *winNum, int instId, int hookId, void *addr, unsigned nBytes, const char *symVarName) {
#ifdef MEMOIZER_ORDER	
#ifdef ENFORCE_WINDOW
	mmz_print("MyTid %d taskStart %d\n", ternMyTid(gettid()), queue->getInTaskThreadNum());
	// There must not be more than TASK_WINDOW_SIZE in a window.
	do {
		waitForTurn(__FUNCTION__, 0);
		giveUpTurn(__FUNCTION__, 0);
	} while (queue->getInTaskThreadNum() == (int)TASK_WINDOW_SIZE);

	*winNum = globalWindowSerialNum;

	mmz_print("MyTid %d taskBegin after wait %d\n", ternMyTid(gettid()), queue->getInTaskThreadNum());
	if (queue->getInTaskThreadNum() == 0) {
		while (!windowTidTotalOrder.empty()) {
			// Do not free it, because the sched cache needs to use recorded trunk (with this heap memory) to compare with new recorded trunk.
			//char *s = windowTidTotalOrder.at(0);
			windowTidTotalOrder.erase(windowTidTotalOrder.begin());
			//free(s);
		}
		char buf[64] = {0};
		sprintf(buf, "START_TERN_WINDOW %d", globalWindowSerialNum);
		appendLandmarkOp(buf, 1, NULL);
		memAccess.loggingMemAccess = true;
		windowConstraintString = "";
		schedCache->createMemoizedSched();
	}
	queue->setInTaskThreadNum(queue->getInTaskThreadNum() + 1);
	mmzEnterTaskTidOrder[ternMyTid(gettid())] = queue->getInTaskThreadNum();
	isInTask[queue->getTidMap()] = 1;
	appendTidTotalOrder(START_TASK_LANDMARK, queue->getTidMap(), instId, NULL, NULL, hookId);
	fprintf(stderr, "MyTid %d taskBegin return %d\n", ternMyTid(gettid()), queue->getInTaskThreadNum());
#endif
#else
	queue->setInTaskThreadNum(queue->getInTaskThreadNum() + 1);
	if (queue->getInTaskThreadNum() == 1) {
		memAccess.loggingMemAccess = true;
	}
	*winNum = globalWindowSerialNum;
#endif
}

int Memoizer::taskEnd(int *winNum, int instId, int hookId) {
#ifdef MEMOIZER_ORDER
#ifdef ENFORCE_WINDOW
	fprintf(stderr, "MyTid %d taskEnd inNum %d, outNum %d\n", 
		queue->getTidMap(), queue->getInTaskThreadNum(), queue->getOutTaskThreadNum());
	int result = 0;
	char fileName[SMALL_SIZE] = {0};

	sprintf(fileName, CONSTRAINT_FILENAME, DUMP_DIR, *winNum, ternMyTid(gettid()), gettid());
	std::string temp = &(fileName[0]);
	appendWindowString(temp);

	// HEMING: CONFUSED HERE, SINCE WE DO NOT HAVE TOKEN FOR TASK END? WE HAVE REMOVED IT?
	waitForTurn(__FUNCTION__, 0);
	queue->setOutTaskThreadNum(queue->getOutTaskThreadNum() + 1);
	appendTidTotalOrder(END_TASK_LANDMARK, queue->getTidMap(), instId, NULL, NULL, hookId);
	
	if (queue->getOutTaskThreadNum() == (int)TASK_WINDOW_SIZE) {
		fprintf(stderr, "MyTid %d taskEnd WINDOW END %d\n", queue->getTidMap(), queue->getInTaskThreadNum());
		char buf[64] = {0};
		sprintf(buf, "END_TERN_WINDOW %d", globalWindowSerialNum);
		appendLandmarkOp(buf, 1, NULL);
		//dumpTidsToFile();
		printMemAccess();
		memAccess.loggingMemAccess = false;
		globalWindowSerialNum++;
		queue->setInTaskThreadNum(0);
		queue->setOutTaskThreadNum(0);
		mmzEnterTaskTidOrder.clear();
		result = 1;

		// Jingyue: Grab the file lock
		if (REPLAYER_LOAD_CACHE && RECORD_ON_FAILURE) {
			int fl = open("/tmp/tern.lock", O_CREAT | O_RDWR, 0777);
			flock(fl, LOCK_EX);
			// Heming: append to schedule cache after a complete window finishes.
			schedCache->storeCache(*winNum);
			flock(fl, LOCK_UN);
			close(fl);
		} else {
			schedCache->storeCache(*winNum);
		}
	}

	*winNum++;
	order_print("MyTid %d taskEnd return %d, globalWindowSerialNum %d\n", 
		queue->getTidMap(), queue->getInTaskThreadNum(), globalWindowSerialNum);

	// This must be at the last part of the function in order to avoid race of globalWindowSerialNum and other global vars.
	giveUpTurn(__FUNCTION__, 0);
	isInTask[queue->getTidMap()] = 0;
	return result;
#endif
#else
	queue->setOutTaskThreadNum(queue->getOutTaskThreadNum() + 1);
	if (queue->getOutTaskThreadNum() == TASK_WINDOW_SIZE) {
		memAccess.loggingMemAccess = false;
		globalWindowSerialNum++;
		queue->setInTaskThreadNum(0);
		queue->setOutTaskThreadNum(0);
		printMemAccess();
	}
#endif
}

void Memoizer::threadCreateStart(unsigned arg) {

}

void Memoizer::threadCreateEnd(unsigned arg, int pthreadId) {
#ifdef MEMOIZER_ORDER	
	char buf[BASIC_SIZE] = {0};

	queue->incTidMap();
	if (windowTidTotalOrder.size() > 0) {
		char *s = windowTidTotalOrder.back();
		if (strstr(s, "pthread_create")) {
			sprintf(s + strlen(s), "-child-[%d", queue->getTidMap());	// We have enough heap space when creating s.
		}
	}
	//fprintf(stderr, "(%d %d)threadStart queue: %s\n", gettid(), queue->getTidMap(), queue->PrintTids().c_str());
	queue->insertBeforeActiveHead();
	// Since the child is alreay at the head of active queue, do not need to wait for turn.
	// We will need to wake up threads blocking on the active queue, so this operation is necessary.
	giveUpTurn(__FUNCTION__, 0);
	sprintf(buf, "threadStart(My Tid: %d)", queue->getTidMap());
	appendLandmarkOp(buf, 1, NULL);
#endif
}

void Memoizer::threadExit(int *info, int hookId, bool realExit) {
#ifdef MEMOIZER_ORDER	
	char buf[BASIC_SIZE] = {0};

	/*fprintf(stderr, "MYTID %d PTHREAD_SELF %x, Memoizer::threadExit()\n", 
		queue->getTidMap(), (int)pthread_self());*///queue->PrintTids().c_str());
	assert(queue->isTidInActiveQueue());
	waitForTurn(__FUNCTION__, 0);
	order_print("threadExit(My Tid: %d, %d) starts to work %s\n", queue->getTidMap(), (int)pthread_self(), queue->PrintTids().c_str());
	sprintf(buf, "threadExit(My Tid: %d)", queue->getTidMap());
	appendLandmarkOp(buf, 1, NULL);
	if(realExit) {
		appendTidTotalOrder(landmarks[TERN_PTHREAD_EXIT_LANDMARK_IDX], queue->getTidMap(), 0, NULL, NULL, hookId);
	}
	queue->delFromQueue();
	if (queue->isSyncVarInBlockingQueue(pthread_self())) {
		queue->insertPthreadIDAfterActiveTail();		// for the thread waiting at pthread_join.
	} else {
		order_print("ThreadExit %d without any other thread/process waiting at pthread_join\n", (int)pthread_self());
		//assert(false);
	}

        // YJF: need this because this code doesn't call giveUpTurn()
        if(get_option(tern, detect_race))
            theRaceDetector->onReleaseTurn(ternMyTid(gettid()));

	queue->addMyselfToDead();
	// Heming: it seems that we do not need to log this event, since we do not know when a thread will terminate.
	//appendTidTotalOrder("threadExit", queue->getTidMap(), hookId);
	assert(queue->findTidMap(gettid()));
	queue->delTidFromMap(gettid());
	*info = -1;
#endif
}

void Memoizer::beforeLandmark(unsigned arg0, unsigned hookId, int instId, uint64_t arg1, uint64_t arg2, uint64_t arg3/*, std::string callStackStr*/) {
#ifdef MEMOIZER_ORDER
	const char *fName = landmarks[arg0];
	uint64_t *args = (uint64_t *)arg1;
	KInstruction *ki = (KInstruction *)arg2;

	std::string funcName = &(fName[0]);
	fprintf(stderr, "TID %d MYTID %d Memoizer::beforeLandmark arg %u funcName %s, hookId %u, queue %s\n", 
		gettid(), queue->getTidMap(), arg0, funcName.c_str(), hookId, queue->PrintTids().c_str());

	if (funcName == "tern_symbolic")
		ternBeforeMakeSymbolic((const char *)args[4], NULL, instId, hookId);	
	else if (funcName == "pthread_mutex_lock" || funcName == "pthread_mutex_trylock") {
		beforePthreadMutexLock(funcName.c_str(), args, ki, instId, hookId);
	}
	else if (funcName == "pthread_mutex_unlock") {
		beforePthreadMutexUnLock(funcName.c_str(), args, ki, instId, hookId);
	}	
	else if (funcName == "pthread_rwlock_wrlock" || funcName == "pthread_rwlock_trywrlock") {
		beforePthreadRWLock(funcName.c_str(), args, ki, instId, true, hookId);
	}
	else if (funcName == "pthread_rwlock_rdlock" || funcName == "pthread_rwlock_tryrdlock") {
		beforePthreadRWLock(funcName.c_str(), args, ki, instId, false, hookId);
	}
	else if (funcName == "pthread_rwlock_unlock") {
		beforePthreadRWUnLock(funcName.c_str(), args, ki, instId, hookId);
	}

	else if (funcName == "pthread_create")
		beforePthreadCreate(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_join")
		beforePthreadJoin(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "sleep")			// do the same thing as pthread_join.
		beforeSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "usleep")
		beforeSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "nanosleep")
		beforeSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "__sigwait" || funcName == "sigwait")				// for mysqld
		beforeSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "select")				// for mysqld socket.
		beforeSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName.find("pod_check") != std::string::npos)				// for httpd.
		beforeSleep(funcName.c_str(), args, ki, instId, hookId);

	else if (funcName.find("accept") != std::string::npos)
	//else if (funcName == "syscall" && args[1] == SYS_socketcall && args[2] == SYS_ACCEPT)		// this is in uclibc, not an external call.
		beforeAcceptSocket(funcName.c_str(), args, ki, instId, hookId);

	else if (funcName.find("epoll_wait") != std::string::npos)
	//else if (funcName == "syscall" && args[1] == SYS_epoll_wait)		// this is in uclibc, not an external call.
		beforeAcceptSocket(funcName.c_str(), args, ki, instId, hookId);

	else if (funcName == "pthread_cond_signal")
		beforePthreadCondSignal(funcName.c_str(), args, ki, instId, hookId);	
	else if (funcName == "pthread_cond_broadcast")
		beforePthreadCondBroadcast(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_cond_timedwait")
		beforePthreadCondTimedWait(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_cond_wait")
		beforePthreadCondWait(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_barrier_wait")
		beforePthreadBarrierWait(funcName.c_str(), args, ki, instId, hookId);

	fprintf(stderr, "TID %d Memoizer::beforeLandmark RETURN arg %u funcName %s, hookId %u\n", 
		queue->getTidMap(), arg0, funcName.c_str(), hookId);

#else
	const char *fName = landmarks[arg0];
	uint64_t *args = (uint64_t *)arg1;
	KInstruction *ki = (KInstruction *)arg2;
//	int instId = hook_id;

	appendTidTotalOrder(fName, gettid(), instId, args, ki, hookId);
#endif
}

void Memoizer::afterLandmark(pthread_t *tid, unsigned arg0, unsigned hookId, int instId, uint64_t ret_val, uint64_t arg1, uint64_t arg2, uint64_t arg3/*, std::string callStackStr*/) {
#ifdef MEMOIZER_ORDER
	const char *fName = landmarks[arg0];
	uint64_t *args = (uint64_t *)arg1;
	KInstruction *ki = (KInstruction *)arg2;

	std::string funcName = &(fName[0]);
	fprintf(stderr, "MYTID %d Memoizer::afterLandmark arg %u funcName %s, hookId %u\n", 
		queue->getTidMap(), arg0, funcName.c_str(), hookId);

	if (funcName == "tern_symbolic")
		ternAfterMakeSymbolic();	
	else if (funcName == "pthread_mutex_lock" || funcName == "pthread_mutex_trylock") {
		//funcName += callStackStr;
		//fprintf(stderr, "Memoizer::afterLandmark pthread_mutex_lock TID %d MYTID %d\n", gettid(), ternMyTid(gettid()));
		fflush(stderr);
		afterPthreadMutexLock(funcName.c_str(), args, ki, instId, hookId);
	}
	else if (funcName == "pthread_mutex_unlock") {
		//funcName += callStackStr;
		afterPthreadMutexUnLock(funcName.c_str(), args, ki, instId, hookId);
	}	
	else if (funcName == "pthread_rwlock_wrlock" || funcName == "pthread_rwlock_trywrlock") {
		afterPthreadRWLock(funcName.c_str(), args, ki, instId, true, hookId);
	}
	else if (funcName == "pthread_rwlock_rdlock" || funcName == "pthread_rwlock_tryrdlock") {
		afterPthreadRWLock(funcName.c_str(), args, ki, instId, false, hookId);
	}
	else if (funcName == "pthread_rwlock_unlock") {
		afterPthreadRWUnLock(funcName.c_str(), args, ki, instId, hookId);
	}

	else if (funcName == "pthread_create")
		afterPthreadCreate(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_join")
		afterPthreadJoin(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "sleep")			// do the same thing as pthread_join.
		afterSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "usleep")
		afterSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "nanosleep")
		afterSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "__sigwait" || funcName == "sigwait")			// for mysqld
		afterSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "select")				// for mysqld socket.
		afterSleep(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName.find("pod_check") != std::string::npos)				// for httpd.
		afterSleep(funcName.c_str(), args, ki, instId, hookId);

	else if (funcName.find("accept") != std::string::npos)
	//else if (funcName == "syscall" && args[1] == SYS_socketcall && args[2] == SYS_ACCEPT)		// this is in uclibc, not an external call.
		afterAcceptSocket(funcName.c_str(), args, ki, instId, hookId);

	else if (funcName.find("epoll_wait") != std::string::npos)
	//else if (funcName == "syscall" && args[1] == SYS_epoll_wait)		// this is in uclibc, not an external call.
		afterAcceptSocket(funcName.c_str(), args, ki, instId, hookId);
	
	else if (funcName == "pthread_cond_signal")
		afterPthreadCondSignal(funcName.c_str(), args, ki, instId, hookId);	
	else if (funcName == "pthread_cond_broadcast")
		afterPthreadCondBroadcast(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_cond_timedwait")
		afterPthreadCondTimedWait(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_cond_wait")
		afterPthreadCondWait(funcName.c_str(), args, ki, instId, hookId);
	else if (funcName == "pthread_barrier_wait")
		afterPthreadBarrierWait(funcName.c_str(), args, ki, instId, hookId);

	fprintf(stderr, "TID %d Memoizer::afterLandmark RETURN arg %u funcName %s\n", queue->getTidMap(), arg0, funcName.c_str());
#endif
}

// Wait for active turn, this is the most frequent wait for turn operation.
void Memoizer::waitForTurn(const char *landmarkName, unsigned arg, int hookId) {
	struct timespec ts;

	int i = 0;
	while (queue->getActiveHead() != queue->getTidMap()) {
		i++;
		clock_gettime(CLOCK_REALTIME, &ts);
		ts.tv_sec += 1;
		pthread_cond_timedwait(&condVarForActiveTurn, &mutex, &ts);
		//if (i%500 == 0) {
		//order_print("got BROKEN active turn(%s) %d %s\n", funcName, queue->getTidMap(), queue->PrintTids().c_str());
			//break;
		//}
	}
	//order_print("got active turn(%s) %d %s\n", funcName, queue->getTidMap(), queue->PrintTids().c_str());

        if(get_option(tern, detect_race))
            theRaceDetector->onAcquireTurn(ternMyTid(gettid()));
}

// Give up active turn.
void Memoizer::giveUpTurn(const char *landmarkName, unsigned arg) {
	queue->delFromActiveHead();
	queue->insertAfterActiveTail();	

        if(get_option(tern, detect_race))
            theRaceDetector->onReleaseTurn(ternMyTid(gettid()));
}

void Memoizer::recordMemAccess(bool isLocal, ExecutionState &state, KInstruction *ki, int addr, int instId) {
  if (isLocal || ki == NULL)
		return;

  int offset = 0;
  memAccess.loadStoreInstCnt++;

  offset += sprintf(memAccess.InstToAddrMap[memAccess.loadStoreInstCnt] + offset, "%d, ", addr);
  offset += sprintf(memAccess.InstToAddrMap[memAccess.loadStoreInstCnt] + offset, "%d, ", instId);
  for (unsigned i = 0; i < state.stack.size(); i++) {
    StackFrame &sf = state.stack.at(i);
    assert(sf.kf->function->hasName());
    offset += sprintf(memAccess.InstToAddrMap[memAccess.loadStoreInstCnt] + offset, "%s, ", sf.kf->function->getNameStr().c_str());
    assert(offset < BASIC_SIZE);
  }
}

std::string Memoizer::getCallStackStr(ExecutionState &state) {
	char buf[BASIC_SIZE];
	unsigned offset = 0;
	
	memset(buf, 0, sizeof(buf));
	for (unsigned i = 0; i < state.stack.size(); i++) {
		StackFrame &sf = state.stack.at(i);
		assert(sf.kf->function->hasName());
		offset += sprintf(buf + offset, "%s, ", sf.kf->function->getNameStr().c_str());
		assert(offset < BASIC_SIZE);
	}

	return &(buf[0]);
}

bool Memoizer::threadInTask() {
	if (IS_BATCH_PROGRAM) {
		// For batch program, all threads are always in task if not broken.
		assert(isInTask.size() == 1);
		Int_To_Int_Map::iterator itr = isInTask.begin();
		if (itr->second == 0) {
			return false;
		}
		return true;
	}
	
	if (isInTask.find(queue->getTidMap()) == isInTask.end())
		return false;
	return isInTask[queue->getTidMap()];
}

void Memoizer::updateTidMapForFork(int parentTid, int childTid) {
	queue->updateTidMapForFork(parentTid, childTid);
}

void Memoizer::initBranchSlicingModule(Module *m) {
	if (MEMOIZER_CONDITION_SLICING != 1)
		return;

	PassManager pm;
	AnalysisUsage *AU = new AnalysisUsage();
	oBr = new OmitBranch();
	oBr->getAnalysisUsage(*AU);
	pm.add(oBr);
	pm.run(*m);
	brInstOmitted = oBr->getBrInstOmitted();

/*	for (Module::iterator f = m->begin(), fe = m->end(); f != fe; ++f) {
		for (Function::iterator b = f->begin(), be = f->end(); b != be; ++b) {
			for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {     
				Instruction *Inst = i;
				if (isa<BranchInst>(Inst)) {
					BranchInst *branch = cast<BranchInst>(Inst);
					assert(brInstOmitted.find((long)branch) == brInstOmitted.end());
					if (oBr->omit(branch)) {
						brInstOmitted[(long)branch] = 1;
					} else {
						brInstOmitted[(long)branch] = 0;
					}
					//errs() << "Considering branch(" << numOfBrInst << ") " << *branch << ", at BB " << branch->getParent()->getNameStr() 
							//<< ", at Func " << branch->getParent()->getParent()->getNameStr() << ".\n\n\n\n";
				}
			}
		}
	}*/
}

bool Memoizer::omitBranch(BranchInst *branch, ref<Expr> condition) {
	if (MEMOIZER_CONDITION_SLICING) {
		assert(brInstOmitted.find((long)branch) != brInstOmitted.end());
		/*if (brInstOmitted[(long)branch]) {
			if (branch->getParent()->getParent()->getNameStr().find("main") != std::string::npos) {
				errs() << "Omit branch " << *branch << ", at BB " << branch->getParent()->getNameStr() 
					<< ", at Func " << branch->getParent()->getParent()->getNameStr() << ".\n";
				condition->print(std::cerr);
		  		fprintf(stderr, "--------------------------\n\n\n\n");
			}
		}*/
		return brInstOmitted[(long)branch];
	}
	return false;
	/*errs() << "Considering branch " << *branch << ", at BB " << branch->getParent()->getNameStr() 
				<< ", at Func " << branch->getParent()->getParent()->getNameStr() << ".\n";
	
	bool result = oBr->omit(branch);*/
	/*if (result)
		errs() << "Omit branch " << *branch << ", at BB " << branch->getParent()->getNameStr() 
				<< ", at Func " << branch->getParent()->getParent()->getNameStr() << ".\n";*/
}


int Memoizer::mmzEnterTaskOrder() {
	if (IS_BATCH_PROGRAM)
		return 0;
	else
		return mmzEnterTaskTidOrder[ternMyTid(gettid())];
}

int Memoizer::mmzTaskConcreteBytes(void *addr) {
	if (!IS_BATCH_PROGRAM) {
		char *buf = new char[BASIC_SIZE];
		memset(buf, 0, BASIC_SIZE);
		char *p = (char *)addr;
		memcpy(buf, p, BASIC_SIZE - 1);
		taskConcreteBytes.push_back(buf);
		if (taskConcreteBytes.size() == TASK_WINDOW_SIZE) {
			char fileName[BASIC_SIZE];
			memset(fileName, 0, BASIC_SIZE);
			sprintf(fileName, "%s/Tid-%d-Tasks-gettid-%d.txt", DUMP_DIR, globalWindowSerialNum-1, gettid());
			std::ofstream taskFile(fileName);
			for (unsigned i = 0; i < taskConcreteBytes.size(); i++) {
				for (unsigned j = 0; j < 100; j++)
					taskFile << (int)(taskConcreteBytes[i][j]) << ", ";
				taskFile << "\n\n\n\n\n";
			}
			taskFile.flush();
			taskFile.close();

			for (unsigned i = 0; i < taskConcreteBytes.size(); i++) {
				delete taskConcreteBytes[i];
			}
			taskConcreteBytes.clear();
		}

	}

	return 0;
}

